This invention relates to an improved fingerprint identification system. Fingerprints are routinely used to identify individuals of unknown or uncertain identity, or to verify the identify of a person. A primary application is in law enforcement, and secondary applications are in security, credit, and entitlement program management.
An individual's fingerprints are unique and have been used to learn the identification of an individual by comparison searching through a fingerprint database that contains the name of the possessor of the fingerprints or by comparing a current fingerprint of claimed person to a fingerprint the person filed on record when earlier establishing his or her identity. Standard file image formats have been adopted for recording the 10 finger fingerprint images. The inked impression cards used for recording contain additional textual information specific to the individual, generally information such as: sex, race, height, weight, hair color, eye color, name, and alias names.
Prior art systems for fingerprint identification have included techniques for beating key features of a fingerprint, such as minutiae, which are features defined by bifurcations or endings of ridge flows in an image of the fingerprint, and for locating and identifying other features, such as cores and deltas, in order to classify fingerprints into class types of whorls, loops, arches, tented arches. It is important that few key features be missed and few false features be recorded. Prior art systems, however, have not provided a complete or reliable extraction of important fingerprint features.
There are generally two types of comparison searching. The first search compares a ten-print card to a file of ten-print cards. For ten-print to ten-print comparisons, the particular finger number is known for each fingerprint image; the rolled inked impression images are, in the norm, complete; the orientation of the fingers is known; and the quality of the images is normally good. This is, of coarse the result of imposing a standard format and a known process for registering the inked impressions of the fingerprints on the ten-print cards.
The second search technique is a latent print (or mark) to ten-print cards. A latent print is a fingerprint obtained in the field from the scene of a crime. A latent print image is lifted from some arbitrary surface through a variety of techniques. In contrast with ten-print cards, latent prints are generally partial prints; the finger number is generally not known with certainty; they are of poorer image quality; their orientation is often not known; and there may be only a single fingerprint available for searching.
Sometimes, a third type of search, latent-to-latent, is made when trying to determine if the same unknown person was present at two or more scene of crime locations.
Fingerprint images today are available on ten-print cards, which are digitized and stored electronic computer records. They can be received in digital electronic form via radio or wire links from external sources and remote terminals. Real-time or livescan devices obtain fingerprints by means of an optical or ultrasonic scanner that reads a fingerprint directly off of the finger. The real time sharing of information and cross searching across distributed network fingerprint databases is the current direction for fingerprint identification systems operation.
When a fingerprint database becomes large, it becomes unmanageable to use human experts to perform the searching operation, therefore the need for automated systems. Automated systems, which have been in operation for over 20 years, examine the images and extract and store the features that describe the fingerprint; they also store any supporting alphanumeric textual information appearing on ten-print cards or with the latents, the textual data is that which would be of benefit in performing comparisons.
A typical automated fingerprint identification system includes a set of repository fingerprint cards 10 (FIG. 1 ) which represent an existing database of ten-print cards kept by the FBI, other law enforcement agency, or private security, credit, entitlement or other organization. These cards contain the fingerprints of known individuals, along with other pertinent information. Card 12 represents a single ten-print card of a candidate whose fingerprints are to be compared with those in the existing database 10 and latent print 14 represents a single fingerprint of an unknown individual. The candidate and latent prints are also called search prints.
An optical Scanner 20 scans the image of each fingerprint on cards 10 and 12 and latent print 14 to provide a digitized version of the gray scale image of each fingerprint. The digitized fingerprint gray scale images from Scanner 20 may be stored in storage device 25 or sent directly to an Encoder 30. The Encoder 30 extracts certain useful information from the gray scale image, such as the location of fingerprint features of cores, deltas, and minutiae. The Encoder 30 provides certain information to a Classifier 40, which in turn determines the pattern class of each fingerprint. Some automated systems may leave the more difficult and critical operations, such as classification, to manual (operator) means or operator assisted means.
A Products File 50 stores several items of feature information in digital format regarding each fingerprint. While illustrated in FIG. 1 and described herein as a card file, the Products File 50 is typically a digitized computer database. For each fingerprint, the Products File typically stores the pattern class determined by the Classifier, and the core, delta, and minutia information determined by the Encoder 30. A manual input device 55 is also provided to enter pattern class, if necessary, along with any known textual data describing the individual whose fingerprints are recorded. A candidate Products File 60 may be created from either a Search Candidate's print card 12 or a copy of his/her latent print(s) 14.
When conducting a search comparison, the feature information of the Search Candidate is hierarchically and sequentially compared with the textual and feature record for each known individual whose fingerprints reside in the repository for the Products File database.
The components of the system used in searching are depicted in FIG. 2, where the selection and matching of one or more of a candidate's fingerprints, as contained in a candidate's Products File will be described. Information from the repository Products File 50 is made available to a Search Filter 70. This filter limits the number of repository fingerprints to be compared based on textual data and the pattern class of the Search Candidate's fingerprints, and sometimes on additional fine grain classification data. The fingerprints of selected file repository candidates fingerprints from the Search Filter 70 are then compared with the Search Candidate's fingerprints in the Matcher component 80, and finally, the best match is found in selection stage 90.
The search always seeks to find that one to one correspondence of fingerprint features that would provide strong assurance that the search prints and file prints belong to the same individual. The systems typically score the results of the comparisons and produce a rank ordered list of a fixed number of list positions (typically 4 to 10). It is then up to a trained fingerprint examiner to examine the set of search prints in comparison to file sets of prints for the list named File Candidates with highest scores. The examiner must determine whether there is indeed a match to one of the File Candidates appearing on the list.
The sequence of search typically proceeds in a down selection process, first eliminating those File Candidates whose personal descriptions are dissimilar, then those with differing classification, and finally those with differing subordinate classifications. The filter down selection processor narrows the list of File Candidates to successively smaller and smaller lists (that is, fewer candidates).
The Matcher component 80 of the system performs the final comparative analysis between search print and each file print. It matches minutiae between search print and file print. Matching minutiae is performed through mathematical calculation that evaluates and scores how closely minutiae in the search print are to having the same spatial and angular positioning as the candidate file print being considered. The evaluative process typically proceeds first to align the two prints, then attempts to find correspondence by pairing minutiae in the search fingerprint with what appears to be its most probable counterparts in the file fingerprint, and then proceeds to calculate and evaluate spatial and angular differences. The comparative process is complete when matching comparisons between Search Candidate prints and all candidate file prints have been made and a score for each file print comparison is available. The scores are then evaluated and those with scores that definitely indicate large dissimilarity in minutiae pattern are eliminated from the list. The remainder of the list contains File Candidates with similar and closely matching minutiae patterns. The higher the score the more that the Search Candidate's fingerprints closely match the File Candidate's fingerprints and the greater probability that the Search Candidate is the same as the File Candidate person on record in the repository file database. The list is rank ordered and the top scoring "n" number of candidates presented to the operator; the number "n" typically being set at the system operator's discretion.
For ten-print to ten-print searches, the operator also typically has the option to select the number of fingers to be compared (1 to 10) and to designate the specific fingers to be used in the comparative searches. Use of more fingers provides a more discriminating selection (greater selectivity) but entails considerably more time in performing minutiae matching. For latent to ten-print searches, the operator's options are greater, as it frequently is not known exactly which numbered finger the latent print is from. Hence the latent print must be searched across multiple fingers of each file ten-print record.
A coarse level of fingerprint identification is available by examining macro fingerprint features, namely cores and deltas. Core and delta placements give rise to higher level descriptors that characterize similarity. Pattern type descriptors are defined by the Henry system and the FBI's National Crime Information Center system. The loop, whorl, and arch are examples. A series of second level descriptors are used to further associate similar fingerprints into like groupings. For example, for whorls, a second level descriptor indicates whether the ridge contour just below the left delta is inside, outside, or meets the right delta.
These coarse level descriptors are stored away for each file print and are used as sort discriminates by applying various techniques such as ordered list sorting, storage binning, and retrieval access methods. These techniques aid and provide for efficiency of process in the early stages of down selection. Since the comparative discriminates are macro level features, there still remains a large number of File Candidates that posses equivalent descriptions of their characteristics, and hence must be passed on to a Minutiae Matcher for calculating comparisons to be performed.
If other pre-measured macro feature characteristics could be used in the sorting process along with the macro features, the list could be further limited before passing on to the Minutiae Matcher component. There are such features, but prior art automatic systems have not been able to effectively employ them, primarily for two reasons: prior art systems do not reliably find or accurately identify the x,y location of macro features, and they do not have processes that provide for routinely extracting ridge count measurements between macro features.
Prior art matchers try to superimpose two sets of minutiae points in order to count the number of minutiae which are in common to the two fingerprints. Some typical prior art matchers are the M19, M27, M32, M40, M41 and M82. They are described in the following publications: National Bureau of Standards (NBS) Technical Notes 538 and 878, and NBS Special Publication 500-89.
In the final analysis, the list of high scoring matches presented to the operator requires an expert examiner visually to compare the fingerprints of the Search Candidate to each of the listed close match File Candidates. This manual labor step and the number of fingerprint comparisons that the examiner must view places limits on the throughput, the turn around time of the system, and drives the life cycle cost of operation.
If an automatic system could be verified as highly reliable and as having the selectivity to always identify the exact matches, a final list could be limited to one, two or three, and the corresponding examiner workload reduced. The problem is that prior art systems are not highly reliable or selective, as commonly acknowledged and addressed in many patent applications in the area. They require uniform, high quality images to function reliably and consistently. As a result they do not handle latents very well, and they frequently have difficulty with the image variations that occur on ten-print card images.
Non ideal image quality as a result over inking, low contrast, scratches, and pencil marks cause prior art automatic encoders to produce false minutiae, fail to record real minutiae and macro features, and mis-locate real features. Additionally, acquired artifacts in the fingerprint itself, such as cuts, scrapes, abrasions, and scars, can cause the systems to similarly fail to reliably identify real features. A description of these shortcomings may be found described in prior U.S. Pat. Nos. 4,790,564, 4,047,154, 4,646,352, 4,015,240 and 5,040,224. In fact, there are some prior art patents that accept the automation shortcomings as insurmountable and describe systems designed with a human in the loop to perform the classification, feature checks, and other processes not reliably left to prior art automation. U.S. Pat. Nos. 4,047,154 and 4,607,384 are two such examples.
When false features are inserted, or existing features missed or improperly encoded, the workload for the Minutiae Matcher will be increased and the scoring discriminate peaks reduced as a result of noise and errors that add in along with the real score contributors. Consequently, reliability is down, the final list must contain more candidates to insure a real match is assured of making the list, and therefore the human examination workload increases. The shortcomings of the prior art systems are routinely compensated for by an examiner reviewing the automatic encoder results and manually removing false minutiae, entering information on missed features and minutiae, and correcting positional errors.
The larger the database of file prints becomes, the more impractical it becomes to rely on passing on automatic machine determinations to an operator for quality checks and corrections. The more examiners involved, the greater the differences of results and biases introduced will become.
Also, latent prints and their lower quality are frequently not trusted to an automated encoder at all, but rather are manually encoded. The requirement for a human workload element has significant negative impact in throughput, response time, and costs irrespective of which step in the process it is introduced. So much so that the subject of other patents has been to find methods of performing the minutiae pairings in the minutiae matching process to minimize the detuning of discrimination that comes from the presence of false minutiae and to introduce quality reference as an adjustment in scoring. See for example U.S. Pat. No. 4,790,564.
Prior art systems for fingerprint identification have included techniques for locating key features of a fingerprint such as minutiae, which are features defined by bifurcations or abrupt endings of ridge flows in an image of the fingerprint, and for locating and identifying other features, such as cores, deltas, loops, arches, tented arches and other visually discernible characteristics of the fingerprint. It is important that most key features be found and few false features be recorded. Prior art systems, however, have not provided a complete or reliable extraction of important fingerprint features.
The present database of fingerprints in the FBI archives includes approximately 30 million ten-print cards. In addition to an individual's actual fingerprints, these cards contain other information about that person, such as age, eye and hair color, height, race, sex, weight and the type of crime committed.
In a comprehensive system, one must not only compare a newly created or Search Candidate ten-print card to the repository database, but one must also be able to compare a single, perhaps latent, print with the database. This requirement makes it critical that each fingerprint's features be carefully and accurately extracted and properly classified in order to make search comparison and matching possible in the shortest amount of time.
In prior art systems, an image of each fingerprint is often converted from a gray scale image to a binarized (black and white) version before feature extraction is performed which can cause valuable information to be missed and false minutia to be produced. Further, such systems cannot distinguish poor quality images from those of good quality, resulting in less than optimum performance.
Accordingly, there is a need for an improved fingerprint identifying system which provides for the accurate identification of fingerprint features and for rapid comparison of a candidate's fingerprint with those fingerprints of individuals in the repository database.